package 所有可达路径;

import java.util.*;

/**
 * @author: AirMan
 * @date: 2025/5/28 15:15
 * @description:
 * 【题目描述】
 * 给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个程序，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
 * 【输入描述】
 * 第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边
 * 后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径
 * 【输出描述】
 * 输出所有的可达路径，路径中所有节点的后面跟一个空格，每条路径独占一行，存在多条路径，路径输出的顺序可任意。
 * 如果不存在任何一条路径，则输出 -1。
 *
 * 数据范围：
 * 图中不存在自环
 * 图中不存在平行边
 * 1 <= N <= 100
 * 1 <= M <= 500
 */
public class Solution {
    public static void main(String[] args) {
        // 图采用邻接矩阵的方式实现
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 节点数
        int[][] graph = new int[n + 1][n + 1]; // 采用邻接矩阵存储
        int m = sc.nextInt(); // 边数
        for (int i = 1; i <= m; i++) {
            // s -> t 存在路径
            int s = sc.nextInt();
            int t = sc.nextInt();
            graph[s][t] = 1;
        }
        path.add(1);
        dfs(graph, 1, n, n);

        for (List<Integer> path : result) {
            for (int i = 0; i < path.size(); i++) {
                System.out.print(path.get(i));
                if (i != path.size() - 1) {
                    System.out.print(" ");
                } else {
                    System.out.println();
                }
            }
        }
    }

    private static List<List<Integer>> result = new ArrayList<>();
    private static List<Integer> path = new ArrayList<>();

    public static void dfs(int[][] graph, int start, int end, int n) {
        if (start == end) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (graph[start][i] != 1) {
                continue;
            }
            path.add(i);
            dfs(graph, i, end, n);
            path.remove(path.size() - 1);
        }
    }
}
